University of Alberta computer scientist Jonathan Schaeffer ate, slept and breathed the game of checkers for the last 18 years. In 1989, Schaeffer programmed a computer named Chinook to begin the calculations that would eventually "solve" the game, reaching the conclusion - on April 29 - that a perfectly played match will always result in a draw.

With 500 billion billion possible positions, checkers is now the most complicated game to be "solved" (beating past record-holder, Connect Four).

Macleans.ca: Why do you think this story's generated so much interest?

Jonathan Schaeffer: I'm not sure - you tell me! I mean, it's checkers being solved and a perfect match resulting in a draw. Is all of that exciting? Probably not. [But] I once saw a survey that said that over 90 per cent of North Americans had played checkers, while less than 50 per cent had played chess. And in part that's because of the simple, elegant rules that checkers has. So that's part of the story. Maybe - I hate to say this - people think of this mad computer scientist who persevered after 18 years.

M: So how does it feel, after 18 years, to finally have reached the end goal?

JS: Surreal. When it happened, I wasn't expecting it. I was in California on a business trip and I knew that it was going to end soon, but it's hard to predict. I just showed up at a hotel, and the first thing I did, as I've done for 18 years, multiple times a day, I immediately logged in to check on the status of the computations, and was very upset because all the computers were apparently not running. I thought, "Oh no, the computers are crashed, maybe there's been a power outage, something's wrong." And when I checked the log file it said, "Draw." I was just stunned. It was over and everything had stopped because there was nothing left to do - it had answered the question. There it was. It took me a few days to break out of the habit of checking in on the computer multiple times a day. Doing it every day for 18 years, I would never go anywhere, even on holidays, without my laptop... In two weeks I go on holidays with my family and I'm not even bringing a computer. I'm going to have three weeks with no computer. This is like the first time since my undergraduate days, 30 years ago. It's scary. You can't imagine how thrilled my wife is.

M: Is checkers still even a popular game?

JS: Depends what you mean. There is a world championship. Competitive checkers is alive and well, but the big thing here is that most people play checkers as a kid... Now most people, of course, don't carry it on and become obsessed with the game. But it's a lot of fun - you should see our website. We have our [Chinook] programs online so people can play them and in the last 24 hours over 10,000 games have been played. And it's only that small a number because we're limiting the number of people to make sure our computers don't crash.

M: Why do you think all these people want to play against a program that they know is unbeatable - when they know they can't win?

JS: But they can. What we've done is put two programs on the web. Yes, the proof that checkers is a draw is on the web and you can play it if you want, but that's no fun. You know you're not going to win and nobody wants to play a game they can't win.
[So] we [also] put on the web our program from 1994, which won the world championship, and we've set it to various skill levels, including my favourite, which is called "novice." At the novice level, you can win [but] it's sad to say that I've never beaten the program at the novice level. I'm almost embarrassed to admit that to somebody who might put that in print. But it's still a very tough program [and] people are on the web, all trying to win. Everybody thinks that they're good at checkers and a lot of them are getting a rude surprise.

M: Now that you've shown a perfect game will always end in a draw, do you think that will hurt the popularity of checkers?

JS: It won't kill the game. Look, I like to play chess. I learned chess as a kid and I was a serious, competitive person. But I'm realistic enough. I know that around the world, let's say there are 100,000 players that are better than me. But I still play chess for the intellectual challenge, the beauty of the game, the social contacts, the friends that I've made, and the competitive spirit. When Deep Blue came along, all I did was shrug my shoulders and say, "Now instead of 100,000 chess players out there that are better than me, there are 100,001. Who cares?" When it comes to checkers it's no different. No checkers player who's playing for the love of the game is going to be dissuaded just because there happens to be a computer program out there that's perfect.

M: What does all this mean, besides the fact that we now know a perfect game of checkers will end in a draw?

JS: The most important thing to realize about this is that this is over one million times bigger than any other optimal problem that has been solved [including Connect Four]. When you look at scientific literature, the most common paper that you see out there is an incremental advance: "Here's somebody's result and I was able to improve it by 10 per cent," or "Wow, I was able to double the performance." This isn't anything small or incremental - this is over a million times bigger. This is like a quantum leap forward in the size of problems that people have been able to solve.

M: And you're moving on to poker now?

JS: I seem to be addicted to long-running projects. I started poker in 1991, so it's 16 years and counting. What is it with me and long projects? I don't know. It wasn't until 2002 that we had a strong poker program. And by a very odd coincidence, [July 23 and 24] is the first Man-Machine World Poker Championship. Two professional poker players are in Vancouver to play our software. We are the world [computer] champion. Rigth now it's pretty clear that the humans are probably better than the computers. Over the next few years I hope that we can improve our software so that maybe one day we will be the World Man-Machine Poker Champion, not just the World Computer Champion.

M: I think of poker as being about reading people's expressions while they're playing. Can a computer really do that?

JS: The answer is, it doesn't have to. Yes, to many people reading the opponent physically is very important. But against weak players it actually doesn't matter to us, because our program is so strong it crushes weak players. And against strong players, if the program could read them physically then other humans could read them [too], and these players wouldn't be winning [in the first place]. Of course our poker program has the ultimate poker face - it gives away nothing.

M: Are you going to keep playing checkers?

JS: I don't really play checkers, other than my quest to beat that bloody program at the novice level one of these days. I'm playing against Chinook at novice and I've probably played ten games in the last couple days. And I have not won - I have not even drawn any of those games. It will happen one day. I am going to beat this guy. Sorry I called it a guy, I was anthropomorphizing it. I could think of some other choice adjectives I could use to describe this program, but I won't out of courtesy.

Alberta researchers solve checkers